package com.example.demo.tixiban;

/**
 * @author xujm
 * @version V2.4
 *  对于一个数组:
 *     4 2  5 1
 *  (1)2 4|1 5
 *  (2)1 2 4 5
 * @since 2.4.0 2022/2/19 13:09
 */
public class Sort_归并排序 {


    public static void spiltSort(int [] arr,int i,int j){
        if(i < j){
            int middle = (i+j)/2;
            spiltSort(arr,i,middle);
            spiltSort(arr,middle+1,j);
            merge(arr,i,middle,middle+1,j);
        }
    }

    public static void merge(int []arr,int i1,int j1,int i2, int j2){

        int start1 = i1;
        int start2 = i2;
        int [] temp = new int[j2-i1+1];
        int tempIndex = 0;
        while(start1 <= j1 && start2 <=j2){
            if(arr[start1] < arr[start2]){
                temp[tempIndex++]=arr[start1++];
            }else{
                temp[tempIndex++]=arr[start2++];
            }
        }
        while(start1 <= j1){
            temp[tempIndex++]=arr[start1++];
        }
        while(start2 <= j2){
            temp[tempIndex++]=arr[start2++];
        }
        tempIndex=0;
        for(int k =i1;k<=j2;k++){
            arr[k] = temp[tempIndex++];
        }
    }

    public static void main(String[] args) {

        int [] arr = {3,4,1,5,8};
        spiltSort(arr,0,arr.length-1);
        for(int i =0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }
}
